"""
1. 首先，我们在字符串S中使用双指针中的左右指针技巧，初始化left = right = 0，把索引左闭有开[left, right)，
    初始化记录目标字符串哈希表needs，其中存放目标字符串T的字符及其个数；
    初始化一个空哈希表window，用于记录滑动窗口中出现的有效字符，有效字符可能会多次重复，甚至超过目标字符串T中的字符数目；
    初始化记录移动过程有效字符的个数valid，valid==need.size
    初始化一个start，在left每次收缩前，更新start和len，记录每次更新的结果
2. 然后，先不断增加right指针扩大窗口[left, right），
    遇到T中含有的字符，进入判断need.count(c)
        c进入window中
        如果某一个字符的数目已经满足要求 window[c] == need[c]
            更新valid++
        更新right++
    直到窗口的字符串符合要求（包含了T中所有字符），valid == need.size（）
        首先，更新此时的start和len，作为本轮合法的结果，该结果可能是合法的最短字符串，也可能不是
        然后，我们取c = s[left]，该字符串需要取出window,left++
        最后，如果d是need中的有效字符,if need.count(c)
            由于window中的c可能重复了特别多次，超越了目标需求，所以更新valid的时机是if windo[d] == need[d]
                valid --
            window[d] --
        此时我们停止增加right，转而不断增加left指针缩小窗口[left, right），
        更新left++
        
3. 最后,返回最小覆盖子串
"""

import collections

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = collections.defaultdict(int)
        window = collections.defaultdict(int)
        
        for char in t:
             need[char] += 1
             
        left, right = 0, 0
        valid = 0
        start = 0
        min_len = float('inf')
        
        while right < len(s):
            c = s[right]
            
            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1
            
            right += 1
        
            while valid == len(need):
                if min_len > right - left:
                    min_len = right - left
                    start = left
                
                d = s[left]
                
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
                
                left += 1
        return "" if min_len == float('inf') else s[start: start + min_len]